//下面看看平衡搜索树balance search tree
//2-3 search tree 2-3查找树
//2-3查找树中，每个节点都有一个或两个key，有一个key的有两个孩子，有两个key的有三个孩子
//2-3查找树是平衡的
//当进行插入的时候，每次都是本应插入到底部，如果底部是一个单key的节点，则将其变为双key的
//如果是两个key的，则将变为临时的3个key的节点，然后将中等大小的key给父母结点，两个key分解成两个节点作为中等大小key的子结点，
//然后对父母结点重复此过程
//上面就是2-3查找树，性能很好，但是实现起来太复杂，下面有更简单的方法：红黑树，左倾红黑树 left-leaning red-black tree
//用二叉树表示2key的树。也就是使用内部的左倾连接来表示2key，当然他在逻辑结构上还是用2-3查找树来理解，不过是物理表示上用这种方式
//而这种被二叉树表示的2key树内部之间的，本不存在却在物理上存在的链接被看做红色
//有点像是树的孩子兄弟表示法，那个是左孩子右兄弟，这个是红色的链接实际上是2key节点的内部链接，而黑色的链接才是树的真实逻辑链接
//像上面这样考虑的话，我们就知道，不会有节点连续连着两个红色的链接，因为红色的链接在对应的2-3查找树的逻辑结构中代表的是一个2key节点的内部链接
//这也就是红黑树和2-3查找树的对应，也就是说，红黑树是2-3查找树的物理抽象实现
//相较于正常的二叉搜索树，红黑树的大部分操作和他们没有区别，他只是平衡性更好而已。而这需要做的就是在插入过程中保持平衡
//这样的实现可以通过给他添加color属性来得到，这个属性表示其父母节点到他的这条连接的颜色
import java.security.Key;

public class RedBlackBST_my<Key extends Comparable<Key>, Value> extends BST{
    static boolean RED=true;
     private class Node {
         private Key key;           // sorted by key
         private Value val;         // associated data
         private Node left, right;  // left and right subtrees
         private int size;          // number of nodes in subtree
         private Boolean color;

         public Node(Key key, Value val, int size) {
             this.key = key;
             this.val = val;
             this.size = size;
         }
     }
         private boolean IsRed(Node x)
         {
            if(x==null) return false;
            return x.color==RED;
         }
    //有时节点会以错误的方式倾斜，我们通过这种方式使得其改回正确的方向
    //h是2key节点中左边的那个，他应该作为右边key的左子树（在二叉树物理结构中），然而现在的情况相反，他是右边key的父母
    //这里不用检验他们的子节点是否存在，直接换位就行。
    private Node RotateLeft(Node h)
    {
       Node x=h.right;
       h.right=x.left;
       x.left=h;
       x.color=false;
       h.color=RED;
       return x;
    }

    //为了方便插入环节，我们会发现有时候不得不暂时将其转化为右倾，所以需要这个函数
    //和上面的一样，这里的h也是2key节点中作为父母结点的那一个
    private Node RotateRight(Node h)
    {
        Node x=h.left;
        h.left=x.right;
        x.right=h;
        x.color=false;
        h.color=RED;
       return h;
    }

    //一个节点此时两边都是红色了，对应与2-3查找树中的情况就是此时成为了一个临时的3key的节点，而这时需要做的就是拆分，并将中间节点传给父母结点
    //这时候需要把这个节点两边的节点都从红色变成黑色，然后这个节点到父母结点的颜色变成红色
    //也就是h左右孩子都变成黑色，然后h自己变成红色
    private void ColorFlip(Node h)
    {
      h.left.color=false;
      h.right.color=false;
      h.color=RED;
    }

    //重量级的来了。在这里实现一下插入。
    //先按照正常二叉树的方式实现插入，然后再进行左旋,这是一个例子
    //下面是几种情况
    //1.如果只有一个节点，那么插入他的左边，这种情况插完标注红色就可以了;如果插入右边，那么需要插完左旋
    //2.如果有两个节点，就是2key情况的2-3查找树，如果插入到了最右边，也就是比两个key都大，那么需要做的是ColorFlip。
    //也就是拆分，并将中间的key传给父母节点
    //如果插入到了最左边，也就是比两个都小，那么先进行右旋，将中间的那个变成这个2key树的根节点连接其余两个节点(也就是类似于上面这种情况)
    //然后进行颜色反转
    //3.如果新插入的节点大小在两个key之间，还是先正常进行插入，然后再先左旋再右旋再颜色反转
    //4.如果是在底部进行插入，那么需要做的是，先进行标准插入，在进行需要的旋转，然后进行颜色反转，最后得改成左倾得
    //这段代码的关键是将一种情况转换为另一种
    //上面是思路流程，下面是代码流程
    //首先检测新插入节点对应的位置是否是空的，也就是说是否存在相同节点，不存在则创建得到新节点继续进行插入，color设置成RED
    //然后通过标准BST流程插入进去
    //最后按照左旋右旋颜色反转的顺序进行筛选，满足条件则进行操作
    public void Insert(Key key,Value value)
    {
      if(key==null)
      {
        throw new IllegalArgumentException("first argument to put() is null");
      }
      if(value==null)
      {
        delete(key);
        return ;
      }
       root=Insert(root,key,value);
    }

    public Node Insert(Node h,Key key,Value value)
    {
       if(h==null) return new Node(key, value, 1);

       //递归实现插入
       int cmp=key.compareTo(h.key);
       if(cmp>0) h.right=Insert(h.right, key, value);
       else if(cmp<0) h.left=Insert(h.left, key, value);
       else h.val=value;

       //这里实现平衡
       if(IsRed(h.right)&&!IsRed(h.left)) h=RotateLeft(h);
       if(IsRed(h.left)&&IsRed(h.left.left)) h=RotateRight(h);
       if(IsRed(h.right)&&IsRed(h.left))  ColorFlip(h);

       return h;       
    }
    
    //关于删除
    //用常规的hibert删除是会出现问题的，得有不破坏平衡性的删除办法，虽然在红黑树实现很困难
    

    //B-tree是红黑树常用的一个应用
    //在操作系统等的文件应用上非常常见
    //思想上好像差不多，不过我没看懂，以后学操作系统的时候再具体看吧
}
